"""
Code to recursively partition one table into a tree of tables 
(a.k.a. dendograms).

This code is part of KNIFE: cropping complexity, culling confusion, 
and cutting the crap since 2012
   
           .----------------._________________
           |=()=========---  \-----------     `\ 
      jgs  \_________________/^^^^^^^^^^^^^^^^^^

(c) 2012, Tim Menzies, tim@menzies.us, LGPL v3.0
"""

from dict import *
import random

def idea(divisor,level=0,enough=0, ripe=0.5,min=4) :
  "Top level driver for the recursive division."
  size   = len(divisor.table.data)
  enough =  enough or max(min,size**ripe)
  divisor.parts(enough)
  for kid in divisor.kids:
    idea(kid, level+1,enough=enough)
  return divisor

class Divide(object) :
  """
  A Divide is an Table with zero or more sub-tables. Kids are
  generated via the max-distance heuristic; i.e. (1) project all
  points onto a line drawn between the two most distant points 
  in the table; (2) split the data at the median point of that line;
  (3) recurse on the two halves.
  """

  def __init__(self,table):
    """
    The two most distance points are 'west' and 'east' and have
    distance 'c' between them. The projection of all points between
    is computed and caches in 'xs'. 
    """
    self.table=table
    self.west = self.east = self.c = 0
    self.xs   = Dict()
    self.fast = True
    self.kids= [] 
    self.westeast()

  def expected(self) :
    "Ask the class what value it expects over this table."
    return (self.table.meta)[-1].all().expected() 

  def wiggle(self):
    "Ask the class what wiggle it expects in the expected value."
    return (self.table.meta)[-1].all().wiggle() 

  def nearest(self,cells) :
    """
    Explore my kids looking for the table closest to 'cells' 
    (and 'cells' is a list of strings or floats)
    """
    if not self.kids:
      return self
    west     = self.table.data[self.west]
    fromLeft = self.table.dist1(west,cells)
    if fromLeft <= self.maxLeft:
      return self.kids[0].nearest(cells)
    else:
      return self.kids[1].nearest(cells)

  def __repr__(self) :
    "Pretty print for this table."
    e = self.expected()
    w = self.wiggle()
    leafp = "  " if  self.kids else " y"
    if nump(e): e="%7.2f" % e
    str = "%5.0f %6.2f %s %7.2f %s" % \
        (len(self.table.data),self.c,e,w,leafp)
    return str.ljust(40)

  def hprint(self,level=0) :
    "Pretty print for a tree of tables."
    if level == 0:
      print "    n  width   xpect  wiggle leaf?"
      print "-----  -----   -----  ------ -----"
    print str(self) + '|..' * level
    for kid in self.kids:
      kid.hprint(level+1)          

  def last(self) : 
    "Returns max index of data."
    return len(self.table.data) 

  def westeast(self) :
    """
    Finds the two most distant points. If 'fast', it
    uses the linear-time FastMap trick (pick anything, 'west' is
    furthest from that, and 'east' is furthest from west). If
    'slow', it does and all pairs comparison.
    """
    if self.fast:
      any = random.randint(0,self.last() - 1)
      self.west = self.table.outmost(any)[0]
      (self.east, self.c) = self.table.outmost(self.west)
    else:
      (self.west,self.east,self.c) = self.table.outmost2()
    return self.west, self.east            

  def x(self,r) :
    """
    Projects row with index 'r' onto the west-east line.
    For effeciency's sake, this result is cached in 'xs'.
    """
    return self.xs.at(r,
                      lambda: self.x0(self.table.dist(r,self.west),
                                      self.table.dist(r,self.east)
                                      ))

  def x0(self,a,b) :
    """
    Primitive for projecting a line with distance 'a' and 'b'
    to 'west' and 'east' onto the west-east line.
    """
    if a >= self.c: return self.c
    if b >= self.c: return 0
    return  (a**2 + (self.c)**2 - b**2) / (2*self.c)

  def projections(self):
    "Returns all the projections, sorted."
    return (
      sorted([self.x(r)
              for r in range(self.last())]))

  def parts(self,enough=4) :
    "Splits the data on the median point of the projections."
    now = len(self.table.data)
    if now >= enough:
      self.maxLeft = medianSorted(self.projections())
      if self.maxLeft:
        left  = []
        right = []
        for r in range(self.last()):
          row  = self.table.data[r]
          what = left if self.x(r) <= self.maxLeft else right
          what.append(row)  
        if enough <= len(left) < now and enough <= len(right) < now:
          self.kids.append(Divide(self.table.clone(left)))
          self.kids.append(Divide(self.table.clone(right)))
    return self
